package com.zj.leetcode.hard.dynamicProgramming;

/**
 * @program: algorithm
 * @description: 买卖股票的最佳时机 III
 * 123 best-time-to-buy-and-sell-stock-iii
 * @author: Zhang Bo
 * @create: 2022-05-09 11:16:05
 **/
public class BestTimeToBuyAndSellStockIii {
    public static void main(String[] args) {
//        int[] prices = new int[]{1,2,3,4,5};
//        int[] prices = new int[]{6,1,3,2,4,7};
        int[] prices = new int[]{1,2,4,2,5,7,2,4,9,0};
        Solution solution = new BestTimeToBuyAndSellStockIii().new Solution();
        System.out.println(solution.maxProfit(prices));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * [6,1,3,2,4,7]
         * [1,2,4,2,5,7,2,4,9,0]
         * prices = [3,3,5,0,0,3,1,4]
         *
         * @param prices
         * @return
         */
        public int maxProfit(int[] prices) {

            if (prices.length <= 1) {
                return 0;
            }
            int days = prices.length;
            int lastDay = prices[0];
            int firstAmount = 0;
            int secondAmount = 0;
            int amount = 0;
            for (int i = 1; i < days; i++) {
                if (lastDay < prices[i]) {
                    amount = amount + (prices[i] - lastDay);
                } else {
                    if (firstAmount < amount) {
                        secondAmount = firstAmount;
                        firstAmount = amount;
                    } else {
                        if(secondAmount < amount){
                            secondAmount = amount;
                        }
                    }
                    amount = 0;
                }
                lastDay = prices[i];
            }

            if (firstAmount < amount) {
                secondAmount = firstAmount;
                firstAmount = amount;
            } else {
                if(secondAmount < amount){
                    secondAmount = amount;
                }
            }

            return firstAmount + secondAmount;
        }


        public int maxProfit01(int[] prices) {
            /**
             对于任意一天考虑四个变量:
             fstBuy: 在该天第一次买入股票可获得的最大收益
             fstSell: 在该天第一次卖出股票可获得的最大收益
             secBuy: 在该天第二次买入股票可获得的最大收益
             secSell: 在该天第二次卖出股票可获得的最大收益
             分别对四个变量进行相应的更新, 最后secSell就是最大
             收益值(secSell >= fstSell)
             **/
            int fstBuy = Integer.MIN_VALUE, fstSell = 0;
            int secBuy = Integer.MIN_VALUE, secSell = 0;
            for(int p : prices) {
                fstBuy = Math.max(fstBuy, -p);
                fstSell = Math.max(fstSell, fstBuy + p);
                secBuy = Math.max(secBuy, fstSell - p);
                secSell = Math.max(secSell, secBuy + p);
            }
            return secSell;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}